package org.lql.algo.codecrush.week006;

import org.lql.algo.common.ListNode;

/**
 * @author: liangqinglong
 * @date: 2025-08-07 17:51
 * @description: 148. 排序链表 <a href="https://leetcode.cn/problems/sort-list/description/">...</a>
 **/
public class SortList {

	/**
	 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
	 * <p>
	 * 示例 1：
	 * <p>
	 * <p>
	 * 输入：head = [4,2,1,3]
	 * 输出：[1,2,3,4]
	 * 示例 2：
	 * <p>
	 * <p>
	 * 输入：head = [-1,5,3,4,0]
	 * 输出：[-1,0,3,4,5]
	 * 示例 3：
	 * <p>
	 * 输入：head = []
	 * 输出：[]
	 * <p>
	 * 提示：
	 * <p>
	 * 链表中节点的数目在范围 [0, 5 * 104] 内
	 * -105 <= Node.val <= 105
	 */
	public ListNode sortList(ListNode head) {
		if (head == null || head.next == null) {
			return head; // 0 或 1 个节点直接返回
		}

		// 1. 找中点（快慢指针）
		ListNode slow = head, fast = head, prev = null;
		while (fast != null && fast.next != null) {
			prev = slow;
			slow = slow.next;
			fast = fast.next.next;
		}
		prev.next = null; // 断开前半部分

		// 2. 递归排序左右两半
		ListNode l1 = sortList(head);
		ListNode l2 = sortList(slow);

		// 3. 合并两个有序链表
		return merge(l1, l2);
	}

	private ListNode merge(ListNode l1, ListNode l2) {
		ListNode dummy = new ListNode(0);
		ListNode curr = dummy;

		while (l1 != null && l2 != null) {
			if (l1.val <= l2.val) {
				curr.next = l1;
				l1 = l1.next;
			} else {
				curr.next = l2;
				l2 = l2.next;
			}
			curr = curr.next;
		}
		if (l1 != null) curr.next = l1;
		if (l2 != null) curr.next = l2;

		return dummy.next;
	}

	public static void main(String[] args) {
		SortList sortList = new SortList();
		ListNode node1 = new ListNode(4);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(1);
		ListNode node4 = new ListNode(3);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		ListNode result = sortList.sortList(node1);
		ListNode.printList(result);
	}
}
